/*
 * @lc app=leetcode.cn id=148 lang=cpp
 *
 * [148] 排序链表
 */

#include <limits.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);
    }

    // 对 [head, tail - 1] 范围内的节点进行排序
    ListNode* sortList(ListNode* head, ListNode* tail) {
        // 递归终止条件：需要排序 0 个节点
        if (head == nullptr) return head;
        // 递归终止条件：需要排序 1 个节点
        if (head->next == tail) {
            head->next = nullptr;
            return head;
        }

        // 快慢指针寻找链表中点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != tail) {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail) {
                fast = fast->next;
            }
        }
        ListNode* mid = slow;

        return mergeTwoList(sortList(head, mid), sortList(mid, tail));
    }

    ListNode* mergeTwoList(ListNode* head1, ListNode* head2) {
        // 插入伪头部
        ListNode* dummyNode = new ListNode(0);
        ListNode* temp = dummyNode;     // 结果链表的指针
        ListNode* temp1 = head1;        // 第一个链表的指针
        ListNode* temp2 = head2;        // 第二个链表的指针
        
        // 遍历两个链表直至有一个为空
        while (temp1 != nullptr && temp2 != nullptr) {
            if (temp1->val <= temp2->val) {
                temp->next = temp1;
                temp1 = temp1->next;
            } else {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        
        // 将非空链表插入结果链表中
        if (temp1 != nullptr) {
            temp->next = temp1;
        } else {
            temp->next = temp2;
        }

        return dummyNode->next;
    }
};
// @lc code=end

